class Solution
{
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>> &edges, vector<vector<int>> &queries)
    {
        vector<unordered_map<int, int>> graph(n);
        for (auto &edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph[u][v] = w;
            graph[v][u] = w;
        }

        // dfs, 建立根节点到各个节点的权重计数, 以及树上倍增数组
        vector<vector<int>> weightCount(n, vector<int>(27, 0)); // weightCount[i]为根节点到i号节点的权重计数, 1 <= weight <= 26
        int logDepthUpperBound = log2(n) + 1;
        vector<vector<int>> parents(n, vector<int>(logDepthUpperBound, -1));
        vector<int> depth(n, 0);

        function<void(int, int)> dfs = [&](int node, int parent)
        {
            parents[node][0] = parent;
            for (int i = 1; i < logDepthUpperBound; ++i)
            {
                if (parents[node][i - 1] != -1)
                {
                    parents[node][i] = parents[parents[node][i - 1]][i - 1];
                }
                else
                {
                    break;
                }
            }
            if (parent != -1)
            {
                depth[node] = depth[parent] + 1;
                weightCount[node] = weightCount[parent];
                ++weightCount[node][graph[parent][node]];
            }
            for (auto &[nearNode, weight] : graph[node])
            {
                if (nearNode != parent)
                {
                    dfs(nearNode, node);
                }
            }
        };

        dfs(0, -1);

        // 处理queries
        vector<int> answer;
        for (auto &query : queries)
        {
            int u = query[0];
            int v = query[1];
            int originU = u;
            int originV = v;

            int lca = -1;
            if (depth[u] < depth[v])
            {
                swap(u, v);
            }
            int depthDiff = depth[u] - depth[v];
            for (int i = 0; i < log2(depth[u]) + 0.5; ++i)
            {
                if (depthDiff & (1 << i))
                {
                    u = parents[u][i];
                }
            }
            if (u == v)
            {
                lca = u;
            }
            else
            {
                for (int i = log2(depth[u]) + 0.5; i >= 0; --i)
                {
                    if (parents[u][i] != -1 && parents[u][i] != parents[v][i])
                    {
                        u = parents[u][i];
                        v = parents[v][i];
                        break;
                    }
                }
                while (parents[u][0] != parents[v][0])
                {
                    u = parents[u][0];
                    v = parents[v][0];
                }
                lca = parents[u][0];
            }

            // 计算u,v之间的权重计数, 用u,v到0的计数减去2倍lca到0的计数
            vector<int> weightCountUV(27, 0);
            for (int i = 1; i <= 26; ++i)
            {
                weightCountUV[i] = weightCount[originU][i] + weightCount[originV][i] - 2 * weightCount[lca][i];
            }

            // ans为总和减去最大值
            int ans = accumulate(weightCountUV.begin(), weightCountUV.end(), 0) - *max_element(weightCountUV.begin(), weightCountUV.end());
            answer.push_back(ans);
        }

        return answer;
    }
};